package leetcode.primary;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class T56 {
    List<Section> list;
    public T56(){
        list = new ArrayList<>();
    }
    public int[][] merge(int[][] intervals) {

        for (int[] interval : intervals) {
            list.add(new Section(interval[0], interval[1]));
        }

        Collections.sort(list);
//        for (Section section : list) {
//            System.out.println(section.left+" "+section.right);
//        }
        for (int i = 0; i < list.size()-1; i++) {
            Section front = list.get(i);
            Section after = list.get(i+1);
            boolean flag = combine(front,after,i);
            if (flag){  //由于remove了两个，新增了一个合并的，所以需要i--
                i--;
            }
        }
        System.out.println("--------------------------------");

        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i][0] = list.get(i).left;
            ans[i][1] = list.get(i).right;
            System.out.println(ans[i][0]+" "+ans[i][1]);
        }
        return ans;

    }

    public boolean combine(Section front,Section after,int index){
        if (after.left>front.right){
            return false;
        }
        int left;
        int right;

        left = front.left;
        right = Math.max(front.right,after.right);

        list.add(index,new Section(left,right));
        list.remove(index+1);
        list.remove(index+1);
        return true;
    }

    public static void main(String[] args) {
        T56 test = new T56();
        int[][] intervals = new int[][]{{1,3},{1,4},{2,3},{1,2},{2,2},{3,4},{5,7},{5,8}};
        test.merge(intervals);
    }
}

class Section implements Comparable<Section>{
    int left;
    int right;
    public Section(int left, int right){
        this.left = left;
        this.right = right;
    }
    @Override
    public int compareTo(Section o) {
        if (this.left<o.left){
            return -1;
        }else if (this.left==o.left){
            if (this.right<o.right){
                return 1;
            }else {
                return -1;
            }
        }else {
            return 1;
        }
    }



}